package main.java.indi.zyj.c150.back;

public class _13_SolveSudoku {


    void solveSudoku(char[][] board){

    }


    boolean backtrack(char[][] board, int i, int j){

        int m = 9, n = 9;

        if (i == m) {
            // 找到一个可行解，触发 base case
            return true;
        }


        if (j == n){
            return backtrack(board, i + 1, j);
        }

        if (board[i][j] != '.'){
            return backtrack(board, i, j + 1);
        }

        for (char k = '1'; k < '9'; k++) {
            if (!isValid(board, i, j, k)){
                continue;
            }
            board[i][j] = k;
            if (backtrack(board, i, j + 1)){
                return true;
            }
            board[i][j] = '.';
        }
        return false;
    }

    boolean isValid(char[][] board, int i, int j, char ch){
        for (int k = 0; k < 9; k++) {
            if (board[i][k] == ch){
                return false;
            }
            if (board[k][j] == ch){
                return false;
            }
            if (board[(i/3)*3 + k/3][(j/3)*3 + k%3] == ch)
                return false;
        }
        return true;
    }



}
